{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 排序算法的使用和实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 载入必要的工具\n",
    "# 似乎meishen没什么需要导入的额"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 主要参考文献\n",
    "- [经典排序算法总结与实现 ---python](https://www.cnblogs.com/zhizhan/p/4549099.html):对前7种方法有详细描述，还有很多动图进行描述\n",
    "- [数据结构常见的八大排序算法（详细整理）](https://www.jianshu.com/p/7d037c332a9d)：八大排序，十分详细，有动图描述"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概述\n",
    "八大排序，三大查找是《数据结构》当中非常基础的知识点，在这里为了复习顺带总结了一下常见的八种排序算法。常见的八大排序算法，他们之间关系如下：\n",
    "![排序算法结构图](https://upload-images.jianshu.io/upload_images/1156494-ab4cecff133d87b3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/700)\n",
    "\n",
    "其性能比较如下：\n",
    "![排序算法性能比较](https://upload-images.jianshu.io/upload_images/1156494-62f859c2ac6f95ff.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/630)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 冒泡法 \n",
    "冒泡法是最为简单的算法，重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。\n",
    "![冒泡法](https://upload-images.jianshu.io/upload_images/1156494-936d9f02b6aac880.gif?imageMogr2/auto-orient/strip%7CimageView2/2/w/594)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 冒泡法排序\n",
    "def bubble_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using bubble_sort, the length of input is:  '+str(count))\n",
    "    for i in range(0,count):\n",
    "        for j in range(i+1,count):\n",
    "            if input[i]>input[j]:\n",
    "                input[i],input[j]=input[j],input[i]\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=bubble_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 插入排序 \n",
    "将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。因此直接插入排序可以用两个循环完成\n",
    "![插入排序](http://wuchong.me/img/Insertion-sort-example-300px.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 插入排序\n",
    "def insert_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using insert_sort, the length of input is:  '+str(count))\n",
    "    for i in range(1,count):\n",
    "        key=input[i]\n",
    "        j=i-1\n",
    "        while j>=0:\n",
    "            if input[j]>key:\n",
    "                input[j+1]=input[j]\n",
    "                input[j]=key\n",
    "            j-=1\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=insert_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 希尔排序 \n",
    "将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。\n",
    "![希尔排序](https://upload-images.jianshu.io/upload_images/1156494-80700e24aed3d83e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/700)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[14, 5, 32, 32, 74, 59, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 希尔排序\n",
    "def shell_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using shell_sort, the length of input is:  '+str(count))\n",
    "    gap=round(count/2)\n",
    "    while gap>1:\n",
    "        for i in range(gap,count):\n",
    "            temp=input[i]\n",
    "            j=i\n",
    "            while(j>=gap and input[j-gap]>temp ):\n",
    "                input[j]=input[j-gap]\n",
    "                j=j-gap\n",
    "            input[j]=temp\n",
    "        gap=round(gap/2)\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=shell_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 选择排序\n",
    "依次在数组中找到最小的元素放到新的数组中，新数组就是排好序的数组\n",
    "![选择排序](https://upload-images.jianshu.io/upload_images/1156494-25821a7cb5aec881.gif?imageMogr2/auto-orient/strip%7CimageView2/2/w/606)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 选择排序\n",
    "def select_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using select_sort, the length of input is:  '+str(count))\n",
    "    for i in range(0,count):\n",
    "        min=i\n",
    "        for j in range(i+1,count):\n",
    "            if input[j]<input[min]:\n",
    "                min=j\n",
    "        input[min],input[i]=input[i],input[min]\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=select_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 归并排序\n",
    "依次在数组中找到最小的元素放到新的数组中，新数组就是排好序的数组\n",
    "![归并排序](http://wuchong.me/img/Merge-sort-example-300px.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 归并排序\n",
    "def merge_sort(input):\n",
    "    count=len(input)\n",
    "    if count<=1:\n",
    "        return input\n",
    "#     print('using merge_sort, the length of input is:  '+str(count))\n",
    "    num=int(count/2)\n",
    "    left=merge_sort(input[:num])\n",
    "    right=merge_sort(input[num:])\n",
    "    output=merge(left,right)\n",
    "    return output\n",
    "\n",
    "def merge(left,right):\n",
    "    # 两个数组进行合并\n",
    "    l,r=0,0\n",
    "    output=[]\n",
    "    while l<len(left) and r<len(right):\n",
    "        if left[l]<right[r]:\n",
    "            output.append(left[l])\n",
    "            l+=1\n",
    "        else:\n",
    "            output.append(right[r])\n",
    "            r+=1\n",
    "    output+=left[l:]\n",
    "    output+=right[r:]\n",
    "    return output\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=merge_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 快速排序\n",
    "从序列当中选择一个基准数，将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧\n",
    "![快速排序](http://wuchong.me/img/Quicksort-example.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 快速排序\n",
    "def quick_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using quick_sort, the length of input is:  '+str(count))\n",
    "    return qsort(input,0,count-1)\n",
    "def qsort(input,left,right):\n",
    "#     print('step in qsort',input,left,right)\n",
    "    if left>=right:\n",
    "        return input\n",
    "    key=input[left]\n",
    "#     print('key number:',key)\n",
    "    l,r=left,right\n",
    "    while l<r:\n",
    "        while input[r]>=key and l<r:\n",
    "#             print('l,r:',l,r)\n",
    "            r-=1\n",
    "        while input[l]<=key and l<r:\n",
    "#             print('l,r:',l,r)\n",
    "            l+=1\n",
    "        input[l],input[r]=input[r],input[l]\n",
    "    input[left],input[l]=input[l],input[left]\n",
    "    qsort(input,left,l-1)\n",
    "    qsort(input,r+1,right)\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=merge_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7 堆排序\n",
    "首先将序列构建为大顶堆（父节点大于子节点），取出当前大顶堆的根节点，将其与序列末尾元素进行交换，对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质\n",
    "![堆排序](http://wuchong.me/img/Heapsort-example.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 堆排序\n",
    "def heap_sort(input):\n",
    "    count=len(input)\n",
    "#     print('using heap_sort, the length of input is:  '+str(count))\n",
    "    first=int(count/2-1)\n",
    "    for start in range(first,-1,-1):\n",
    "        max_heapify(input,start,count-1)\n",
    "    for end in range(count-1,0,-1):\n",
    "        input[end],input[0]=input[0],input[end]\n",
    "        max_heapify(input,0,end-1)\n",
    "    return input\n",
    "def max_heapify(input,start,end):\n",
    "    # 最大堆计算\n",
    "#     print(input,start,end)\n",
    "    root=start\n",
    "#     print('root:',root)\n",
    "    while True:\n",
    "        child=root*2+1\n",
    "#         print('child:',child)\n",
    "        if child>end:\n",
    "            break\n",
    "        if child+1<=end and input[child]<input[child+1]:\n",
    "            child=child+1\n",
    "        if input[root]<input[child]:\n",
    "            input[root],input[child]=input[child],input[root]\n",
    "            root=child\n",
    "        else:\n",
    "            break\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=heap_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8 基数排序\n",
    "通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序\n",
    "![基数排序](https://upload-images.jianshu.io/upload_images/1156494-70872a75238d1269.gif?imageMogr2/auto-orient/strip%7CimageView2/2/w/619)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input：[14, 32, 32, 5, 74, 59, 76, 87]\n",
      "output：[5, 14, 32, 32, 59, 74, 76, 87]\n"
     ]
    }
   ],
   "source": [
    "# 基数排序\n",
    "def radix_sort_nums(input):\n",
    "    # 求最大位数\n",
    "    maxNum=input[0]\n",
    "    for i in input:\n",
    "        if maxNum<i:\n",
    "            maxNum=i\n",
    "    times=1\n",
    "#     print(maxNum)\n",
    "    while True:\n",
    "#         print(maxNum%(10**(times)),times)\n",
    "        if maxNum%(10**(times))==maxNum:\n",
    "            break\n",
    "        times+=1\n",
    "    return times\n",
    "def radix_get_num_pos(num,pos):\n",
    "    #找到num从低到高第pos位数\n",
    "    return  int((num/(10**(pos-1))))%10\n",
    "def radix_sort(input):\n",
    "    count_input=len(input)\n",
    "#     print('using radix_sort, the length of input is:  '+str(count_input))\n",
    "    count=10*[None] # 存放桶的数据统计个数\n",
    "    bucket=count_input*[None]\n",
    "    for pos in range(1,radix_sort_nums(input)+1):\n",
    "        # 按照位数进行循环\n",
    "        for i in range(0,10):\n",
    "            # 置空\n",
    "            count[i]=0\n",
    "        for i in range(0,count_input):\n",
    "            # 计算每一位组的个数\n",
    "            j=radix_get_num_pos(input[i],pos)\n",
    "            count[j]=count[j]+1\n",
    "        for i in range(1,10):\n",
    "            # 数组分组节点\n",
    "            count[i]=count[i]+count[i-1]\n",
    "        for i in range(count_input-1,-1,-1):\n",
    "            # 放入数组中\n",
    "            j=radix_get_num_pos(input[i],pos)\n",
    "            bucket[count[j]-1]=input[i]\n",
    "            count[j]=count[j]-1\n",
    "        for i in range(0,count_input):\n",
    "            # 更新数组\n",
    "            input[i]=bucket[i]\n",
    "    return input\n",
    "\n",
    "input=[14,32,32,5,74,59,76,87]\n",
    "print('input：'+str(input))\n",
    "output=radix_sort(input)\n",
    "print('output：'+str(output))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结\n",
    "为了分析每个算法的速度，下面来测试一下下吧"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "随机数生成中，正在生成最大值为100000的随机数3000个\n",
      "随机数生成完成，最大值为：99935 ,最小值为：114\n",
      "冒泡排序\ttotally cost\t 425.23455619812 \tprecision\t 100.0\n",
      "选择排序\ttotally cost\t 263.782501220703 \tprecision\t 100.0\n",
      "希尔排序\ttotally cost\t 4.037380218506 \tprecision\t 100.0\n",
      "归并排序\ttotally cost\t 8.018493652344 \tprecision\t 100.0\n",
      "基数排序\ttotally cost\t 23.058414459229 \tprecision\t 100.0\n",
      "快速排序\ttotally cost\t 368.96800994873 \tprecision\t 100.0\n",
      "堆排序\t\ttotally cost\t 332.022428512573 \tprecision\t 100.0\n",
      "插入排序\ttotally cost\t 339.970111846924 \tprecision\t 100.0\n",
      "completed\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import time\n",
    "import sys  \n",
    "  \n",
    "sys.setrecursionlimit(1000000000) # 修改递归深度\n",
    "\n",
    "maxNum=100000\n",
    "count=3000\n",
    "timeRough=12\n",
    "timeMore=3\n",
    "print('随机数生成中，正在生成最大值为'+str(maxNum)+'的随机数'+str(count)+'个')\n",
    "input=[random.randint(1,maxNum) for i in range(count)]\n",
    "print('随机数生成完成，最大值为：'+str(max(input)),',最小值为：'+str(min(input)))\n",
    "\n",
    "# 冒泡排序\n",
    "startTime=time.time()\n",
    "output=bubble_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('冒泡排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 选择排序\n",
    "startTime=time.time()\n",
    "output=select_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('选择排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 希尔排序\n",
    "startTime=time.time()\n",
    "output=shell_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('希尔排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 归并排序\n",
    "startTime=time.time()\n",
    "output=merge_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('归并排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 基数排序\n",
    "startTime=time.time()\n",
    "output=radix_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('基数排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 快速排序\n",
    "startTime=time.time()\n",
    "output=quick_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('快速排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 堆排序\n",
    "startTime=time.time()\n",
    "output=insert_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('堆排序\\t\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "# 插入排序\n",
    "startTime=time.time()\n",
    "output=insert_sort(input)\n",
    "endtime=time.time()\n",
    "wrongNum=0\n",
    "for i in range(0,count-2):\n",
    "    if(output[i]>output[i+1]):\n",
    "        wrongNum+=1\n",
    "precision=100*(1-wrongNum/count)\n",
    "roughTime=round((endtime-startTime)*(10**timeMore),timeRough)\n",
    "print('插入排序\\ttotally cost\\t',roughTime,'\\tprecision\\t',precision)\n",
    "\n",
    "print('completed')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对比一下这个结果：\n",
    "![排序算法性能比较](https://upload-images.jianshu.io/upload_images/1156494-62f859c2ac6f95ff.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/630)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
